"""
遗传算法求解八皇后问题

问题描述：
    在8×8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不能互相攻击。
    皇后可以攻击同一行、同一列或同一对角线上的棋子。
    
    目标是找到皇后的放置方式，使得所有皇后互不攻击（无冲突）。
    八皇后问题是回溯算法的经典问题，也可用遗传算法高效求解。

算法原理：
    使用遗传算法搜索无冲突的皇后排列：
    - 编码方式：排列编码，每个位置i的值表示第i列皇后所在的行
    - 适应度函数：冲突数的倒数，冲突越少适应度越高
    - 选择方法：轮盘赌选择，基于适应度概率选择
    - 交叉操作：顺序交叉(OX)，保持排列的有效性
    - 变异操作：交换变异，随机交换两个位置的值
    - 终止条件：找到无冲突解或达到最大迭代次数

应用场景：
    八皇后问题是组合优化和约束满足问题的代表，类似技术应用于：
    - 资源调度与分配问题
    - 图着色问题
    - 时间表安排问题
    - 网络路由优化

可视化：
    找到解后绘制棋盘，展示皇后放置位置，红色表示有冲突，黑色表示无冲突。

作者：斯黄
日期：2025年3月4日
"""
import numpy as np
import matplotlib.pyplot as plt

N_QUEENS = 8          # 皇后数量
POP_SIZE = 20         # 种群规模
CROSS_RATE = 0.9      # 交叉概率
MUT_RATE = 0.2        # 变异概率
N_GENERATIONS = 1000  # 最大迭代次数

# 计算冲突数
def calc_conflicts(individual):
    conflicts = 0
    for i in range(N_QUEENS):
        for j in range(i+1, N_QUEENS):
            dx = abs(i - j)
            dy = abs(individual[i] - individual[j])
            if dx == dy: conflicts += 1
    return conflicts

# 适应度函数（冲突越少适应度越高）
def get_fitness(pop):
    conflicts = np.array([calc_conflicts(ind) for ind in pop])
    return 1.0 / (conflicts + 1e-3)  # 避免除零错误

# 顺序交叉
def crossover(parent1, parent2):
    child = [-1]*N_QUEENS
    start, end = sorted(np.random.choice(N_QUEENS, 2, replace=False))
    child[start:end] = parent1[start:end]
    remaining = [g for g in parent2 if g not in child]
    child = [g if g != -1 else remaining.pop(0) for g in child]
    return child

# 交换变异
def mutate(individual):
    if np.random.rand() < MUT_RATE:
        i, j = np.random.choice(N_QUEENS, 2, replace=False)
        individual[i], individual[j] = individual[j], individual[i]
    return individual

# 添加冲突检测函数
def conflict_exists(col, row, individual):
    for c in range(col):
        r = individual[c]
        if r == row or abs(c - col) == abs(r - row):
            return True
    return False

# 修改初始化方法，确保有冲突
def create_individual_with_conflicts():
    ind = list(range(N_QUEENS))
    np.random.shuffle(ind)
    # 确保至少有一个冲突
    while calc_conflicts(ind) == 0:
        np.random.shuffle(ind)
    return ind

# 替换原来的初始化
pop = [create_individual_with_conflicts() for _ in range(POP_SIZE)]

# 添加可视化函数：
def plot_queens(individual):
    plt.figure(figsize=(8,8))
    board = np.zeros((N_QUEENS, N_QUEENS))
    board[::2, ::2] = 1
    board[1::2, 1::2] = 1
    plt.imshow(board, cmap='binary')
    
    for col, row in enumerate(individual):
        plt.text(col, row, '♛', fontsize=30, ha='center', va='center', 
                color='red' if conflict_exists(col, row, individual) else 'black')
    plt.xticks([])
    plt.yticks([])

# 添加最小迭代次数
MIN_GENERATIONS = 10

# 进化过程
for generation in range(N_GENERATIONS):
    fitness = get_fitness(pop)
    best_idx = np.argmax(fitness)
    best = pop[best_idx]
    
    print(f"Gen {generation}: 冲突数 {calc_conflicts(best)}")
    if calc_conflicts(best) == 0 and generation >= MIN_GENERATIONS:
        print("找到解：", best)
        plot_queens(best)
        plt.show()
        break
    
    # 选择
    selected = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True, p=fitness/fitness.sum())
    
    # 交叉变异
    new_pop = []
    for i in range(POP_SIZE//2):
        parent1 = pop[selected[2*i]]
        parent2 = pop[selected[2*i+1]]
        child1 = crossover(parent1, parent2)
        child2 = crossover(parent2, parent1)
        new_pop.extend([mutate(child1), mutate(child2)])
    
    pop = new_pop 